class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
// 创建根节点
const root = new TreeNode("A");
// 创建第二层节点
root.left = new TreeNode("B");
root.right = new TreeNode("C");
// 创建第三层节点
root.left.left = new TreeNode("D");
root.left.right = new TreeNode("E");
root.right.left = new TreeNode("F");
root.right.right = new TreeNode("G");
// 创建第四层节点
root.left.left.left = new TreeNode("H");
root.left.left.right = new TreeNode("I");
/*
 *        A
 *      /   \
 *     B     C
 *    / \   / \
 *   D   E F   G
 *  / \
 * H   I
 */
function breadthFirstSearch(root, target) {
    let path=[]
    if(root===null){
        return false
    }
    const queue=[]
    queue.push(root)
    while(queue.length>0){
        const node=queue.shift()
        path.push(node.value)
        if(node.value===target){
            console.log(path.join(" ——> "));
            return true
        }
        if(node.left) queue.push(node.left)
        if(node.right) queue.push(node.right)
    }

}

console.log(breadthFirstSearch(root,"I"));
